import java.util.LinkedList;
import java.util.List;

public class LengthOfLIS {
    public int lengthOfLIS1(int[] nums) {
        // 通过dp的思路我们可以发现我们在计算最长递增子序列的时候，
        // 只需要知道当前最长递增子序列的最后一个元素
        // 并且还有一个贪心的点，就是满足递增子序列，那么一个数可以接在一个较大数的后面
        // 那么他一定可以接在一个较小数的后面，所以我们可以只用记录当前长度的最小的元素
        List<Integer> list = new LinkedList<>();
        for (int num : nums) {
            if (list.size() == 0) {
                list.add(num);
                continue;
            }
            int i = 0;
            for (; i < list.size() && list.get(i) < num; i++) {

            }
            if (i == list.size()) {
                list.add(num);
            } else {
                list.set(i, num);
            }
        }
        return list.size();
    }

    public int lengthOfLIS(int[] nums) {
        // 通过dp的思路我们可以发现我们在计算最长递增子序列的时候，
        // 只需要知道当前最长递增子序列的最后一个元素
        // 并且还有一个贪心的点，就是满足递增子序列，那么一个数可以接在一个较大数的后面
        // 那么他一定可以接在一个较小数的后面，所以我们可以只用记录当前长度的最小的元素
        List<Integer> list = new LinkedList<>();
        for (int num : nums) {
            if (list.size() == 0) {
                list.add(num);
                continue;
            }
            int i = 0;
            // 在列表中寻找第一个大于num的元素的时候，我们可以发现list列表从0~size-1的元素是递增的
            // 所以我们可以使用二分查找的方法来优化
            // 将list分为两部分，小于num的元素和大于等于nums的元素
            // 因为num可能大于list中的所有元素，所以在二分查找之前可以先判断num是否大于list.size()-1的元素
            if (num > list.get(list.size()-1)) {
                list.add(num);
            } else {
                int index = find(list, num);
                list.set(index, num);
            }
        }
        return list.size();
    }

    private int find(List<Integer> list, int target) {
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            int mid = left + (right-left) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        LengthOfLIS lengthOfLIS = new LengthOfLIS();
        int[] nums = {0,1,0,3,2,3};
        System.out.println(lengthOfLIS.lengthOfLIS(nums));
    }
}
